
\documentclass[a4paper,10pt]{article}
\usepackage{color}
% \usepackage{fancyhdr}
\usepackage[utf8]{inputenc}

\usepackage{enumerate}
\usepackage{latexsym}
\usepackage{amssymb}
\usepackage{ulem}
% \usepackage{ifsym}
\usepackage{graphicx}
%\usepackage[margin=3cm]{geometry}

%\renewcommand{\headheight}{16pt}

%\newcommand{\HRule}{\rule{\linewidth}{0.1mm}}

\begin{document}

%\begin{titlepage}
\begin{center}
	\textsc{\Large Distributed Database Systems (WS 11/12) }\\[0.3cm]
	\textsc{\large Assignment 6}\\[1cm]
        Adam Grycner\\
        Szymon Matejczyk\\
        Guo Xinyi\\
        Yu Chenying\\[1cm]
        \today\\[1cm]
        \rule{\linewidth}{0.1mm}\\
 	%\HRule\\
%	\HRule\\[2cm]
	
\end{center}

\section{Exercise 6.1: CAP Theorem}
\begin{itemize}
 \item C :
 ROWA (low write availability)
 \item C$\&$P :
 primary copy (ensures no two partitions are both able to run transactions), majority consensus, dynamic voting, tree quorum, reconfigurable tree quorum
 \item P$\&$A :
 data patches, snapshot replication, epidemic replication
     \end{itemize}
\section{Exercise 6.2: 2PC}
  \begin{enumerate}[ (a)]
  \item .
\begin{center}
  \begin{figure}[ht]
    \label{F:plot2}
      \includegraphics[width=0.4\textheight]{2PC.png}
  \end{figure}
\end{center}

  \item
  \begin{itemize}
   \item \textit{Client} : force-write, begin log entry\\
 \textit{Client} --prepare--$>$ \textit{travel agency}\\
 \textit{Client} --prepare--$>$ \textit{rental car company}

   \item
 \textit{travel agency} : force-write, begin log entry\\
 \textit{travel agency} : force-write, prepared log entry\\
 \textit{rental car company} : force-write, begin log entry\\
 \textit{rental car company} : force-write, prepared log entry\\
 \textit{rental car company} --yes--$>$ \textit{Client}\\
 \textit{travel agency} --prepare--$>$ \textit{travel wholesaler}\\
 \textit{travel agency} --prepare--$>$ \textit{airline 3}\\
 \textit{travel agency} --prepare--$>$ \textit{airline 4}


    \item
 \textit{travel wholesaler} : force-write, begin log entry\\
 \textit{travel wholesaler} : force-write, prepared log entry\\
 \textit{airline 3} : force-write, begin log entry\\
 \textit{airline 3} : force-write, prepared log entry\\
 \textit{airline 4} : force-write, begin log entry\\
 \textit{airline 4} : force-write, prepared log entry\\
 \textit{airline 3} --yes--$>$ \textit{travel agency}\\
 \textit{airline 4} --yes--$>$ \textit{travel agency}\\
 \textit{travel wholesaler} --prepare--$>$ \textit{airline 1}\\
 \textit{travel wholesaler} --prepare--$>$ \textit{airline 2}


    \item
 \textit{airline 1} : force-write, begin log entry\\
 \textit{airline 1} : force-write, prepared log entry\\
 \textit{airline 2} : force-write, begin log entry\\
 \textit{airline 2} : force-write, prepared log entry\\
 \textit{airline 1} --yes--$>$ \textit{travel wholesaler}\\
 \textit{airline 2} --yes--$>$ \textit{travel wholesaler}

  \item
  \textit{travel wholesaler} --yes--$>$ \textit{travel agency}

  \item
  \textit{travel agency} --yes--$>$ \textit{Client}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   \item \textit{Client} : force-write, commit log entry\\
 \textit{Client} --commit--$>$ \textit{travel agency}\\
 \textit{Client} --commit--$>$ \textit{rental car company}

   \item \textit{travel agency} : force-write, commit log entry\\
 \textit{rental car company} : force-write, commit log entry\\
 \textit{rental car company} --ack--$>$ \textit{Client}\\
 \textit{travel agency} --commit--$>$ \textit{travel wholesaler}\\
 \textit{travel agency} --commit--$>$ \textit{airline 3}\\
 \textit{travel agency} --commit--$>$ \textit{airline 4}


    \item \textit{travel wholesaler} : force-write, commit log entry\\
 \textit{airline 3} : force-write, commit log entry\\
 \textit{airline 4} : force-write, commit log entry\\
 \textit{airline 3} --ack--$>$ \textit{travel agency}\\
 \textit{airline 4} --ack--$>$ \textit{travel agency}\\
 \textit{travel wholesaler} --commit--$>$ \textit{airline 1}\\
 \textit{travel wholesaler} --commit--$>$ \textit{airline 2}


    \item
 \textit{airline 1} : force-write, commit log entry\\
 \textit{airline 2} : force-write, commit log entry\\
 \textit{airline 1} --ack--$>$ \textit{travel wholesaler}\\
 \textit{airline 2} --ack--$>$ \textit{travel wholesaler}

  \item
  \textit{travel wholesaler} --ack--$>$ \textit{travel agency}

  \item
  \textit{travel agency} --ack--$>$ \textit{Client}

 \item \textit{Client} : write, end log entry
  \end{itemize}

  \item Possible optimizations:
  \begin{itemize}
   \item Presumed-abort [if most of the transactions are aborted, presumed-abort is more efficient]
   \item Presumed-commit [if most of the transactions are commit ed, presumed-commit is more efficient]
   \item Read-only Subtree Optimization with Presumed-abort [we can eliminate 'rental car company']
   \item Coordinator Transfer (Dynamic 2PC) [changing structure of tree; travel agency - root ]
  \end{itemize}

  \item
    The number of send communicates and log writes will be the same. However, now the transaction tree will be better balanced, so it's possible that more local transactions will be processed in parallel, what can cause faster transaction execution.
  \item

  \begin{itemize}
   \item
 \begin{bf}(until here the same as above)\end{bf}\\
 \textit{airline 3} --no--$>$ \textit{travel agency}\\
 \textit{airline 4} --yes--$>$ \textit{travel agency}\\
 \textit{travel wholesaler} --prepare--$>$ \textit{airline 1}\\
 \textit{travel wholesaler} --prepare--$>$ \textit{airline 2}

    \item
 \textit{airline 1} : force-write, begin log entry\\
 \textit{airline 1} : force-write, prepared log entry\\
 \textit{airline 2} : force-write, begin log entry\\
 \textit{airline 2} : force-write, prepared log entry\\
 \textit{airline 1} --yes--$>$ \textit{travel wholesaler}\\
 \textit{airline 2} --yes--$>$ \textit{travel wholesaler}

  \item
  \textit{travel wholesaler} --yes--$>$ \textit{travel agency}

  \item
  \textit{travel agency} --no--$>$ \textit{Client}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   \item \textit{Client} : force-write, rollback log entry\\
 \textit{Client} --abort--$>$ \textit{travel agency}\\
 \textit{Client} --abort--$>$ \textit{rental car company}

   \item \textit{travel agency} : force-write, rollback log entry\\
 \textit{rental car company} : force-write, rollback log entry\\
 \textit{travel agency} --abort--$>$ \textit{travel wholesaler}\\
 \textit{travel agency} --abort--$>$ \textit{airline 3}\\
 \textit{travel agency} --abort--$>$ \textit{airline 4}

    \item \textit{travel wholesaler} : force-write, rollback log entry\\
 \textit{airline 3} : force-write, rollback log entry\\
 \textit{airline 4} : force-write, rollback log entry\\
 \textit{travel wholesaler} --abort--$>$ \textit{airline 1}\\
 \textit{travel wholesaler} --abort--$>$ \textit{airline 2}

    \item
 \textit{airline 1} : force-write, rollback log entry\\
 \textit{airline 2} : force-write, rollback log entry\\
 \textit{airline 1} --ack--$>$ \textit{travel wholesaler}\\
 \textit{airline 2} --ack--$>$ \textit{travel wholesaler}

  \item
  \textit{travel wholesaler} --ack--$>$ \textit{travel agency}

  \item
  \textit{travel agency} --ack--$>$ \textit{Client}

 \item \textit{Client} : delete, end log entry
  \end{itemize}
  \item
  \begin{itemize}
   \item
 \begin{bf}(until here the same as above)\end{bf}\\
 \textit{airline 3} --no--$>$ \textit{travel agency}\\
 \textit{airline 4} --yes--$>$ \textit{travel agency}\\
 \textit{travel wholesaler} --prepare--$>$ \textit{airline 1}\\
 \textit{travel wholesaler} --prepare--$>$ \textit{airline 2}


    \item
 \textit{airline 1} : force-write, begin log entry\\
 \textit{airline 1} : force-write, prepared log entry\\
 \textit{airline 2} : force-write, begin log entry\\
 \textit{airline 2} : force-write, prepared log entry\\
 \textit{airline 1} --yes--$>$ \textit{travel wholesaler}\\
 \textit{airline 2} --yes--$>$ \textit{travel wholesaler}

  \item
  \textit{travel wholesaler} --yes--$>$ \textit{travel agency}

  \item
  \textit{travel agency} --no--$>$ \textit{Client}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   \item
 \textit{Client} --abort--$>$ \textit{travel agency}\\
 \textit{Client} --abort--$>$ \textit{rental car company} \\
 \textit{Client} : force-write, rollback log entry\\

   \item
 \textit{rental car company} : force-write, rollback log entry\\
 \textit{travel agency} --abort--$>$ \textit{travel wholesaler}\\
 \textit{travel agency} --abort--$>$ \textit{airline 3}\\
 \textit{travel agency} --abort--$>$ \textit{airline 4} \\
 \textit{travel agency} : force-write, rollback log entry

   \item
 \textit{travel wholesaler} --abort--$>$ \textit{airline 1}\\
 \textit{travel wholesaler} --abort--$>$ \textit{airline 2} \\
 \textit{travel wholesaler} : force-write, rollback log entry\\
 \textit{airline 3} : force-write, rollback log entry\\
 \textit{airline 4} : force-write, rollback log entry

    \item
 \textit{airline 1} : force-write, rollback log entry\\
 \textit{airline 2} : force-write, rollback log entry\\

 \item \textit{Client} : delete, end log entry
  \end{itemize}
  \end{enumerate}
\section{Exercise 6.3: Independent Recovery}
\begin{itemize}
\item Add a new state Willing-to-Commit between Collecting and Commit(when the Coordinator receives yes1 and yes2 in state Collecting, it will go into the state Willing-to-Commit; when the Coordinator is in state Willing-to-Commit, it will send commit1 and commit2 to the participants and turn into state Commit.) \\

Then when there's a failure:

the coordinator fails while in state Initial

    --$>$restarts in the state Initial.

the coordinator fails while in state Collecting

    --$>$restarts in the state Initial with sends the "prepare" messages once more.

the coordinator fails while in state Willing-to-Commit

    --$>$restarts in the state Willing-to-Commit.

the coordinator fails while in state Commit

    --$>$restarts in the state Willing-to-Commit with sends the "commit" messages once more.

the coordinator fails while in state "Abort"
    --$>$restarts in the state "Abort".

one participant fails while in state Initial

    --$>$restarts in the state Abort.

one participant fails while in state Prepared

    --$>$restarts in the state Abort. However, if the participant receives the "commit" message again from the Coordinator, it will go into the state Commit.

one participant fails while in state Commit or Abort

    --$>$restarts in the state Commit or Abort.

Now we can see a participant can independently recover from a failure without further interaction.

\item If more than one participant can fail, then we cannot decide to abort the transaction, since some other participants may be in a Commit state. Likely, we cannot commit, either, since some other participants may be in the Abort state. \\
\end{itemize}
\end{document}
